//给你一个字符串 s 、一个字符串 t 。
//返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
//注意：
//对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
//如果 s 中存在这样的子串，我们保证它是唯一的答案。

//示例 1：
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
//解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
//示例 2：
//输入：s = "a", t = "a"
//输出："a"
//解释：整个字符串 s 是最小覆盖子串。
//示例 3:
//输入: s = "a", t = "aa"
//输出: ""
//解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//因此没有符合条件的子字符串，返回空字符串。

//提示：
//m == s.length
//        n == t.length
//1 <= m, n <= 105
//s 和 t 由英文字母组成



#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

//没有大问题，可以用两个哈希表来维护查找过程
//对于 t中没有的元素不必查找
class Solution {
public:
    string minWindow(string s, string t) {
        int s_len = s.size(), t_len = t.size();
        if (t_len> s_len) return string{};
        int l=0, r=0;
        int vector_len = 52;
        vector<int> t_nums(vector_len, 0), s_nums(vector_len, 0);
        using substring = pair<int, int>; // 子串长度， 子串的起点
        vector<substring> substrings{};

        //init t_nums
        for (char ch : t){
            ++t_nums[get_index(ch)];
        }

        //r是尾后迭代器，最后一次也要考虑
        while (r!= s_len){
            if (t_in_s(t_nums, s_nums)){
                while(l<r and t_in_s(t_nums, s_nums)){
                    --s_nums[get_index(s[l])];
                    ++l;
                }
                substrings.push_back({r-l+1, l-1});
            }
            ++s_nums[get_index(s[r])];
            ++r;
        }
        if (t_in_s(t_nums, s_nums)){
            while(l<r and t_in_s(t_nums, s_nums)){
                --s_nums[get_index(s[l])];
                ++l;
            }
            substrings.push_back({r-l+1, l-1});
        }



        if (!substrings.empty()){
            int start = substrings[0].second;
            int minLen = substrings[0].first;
            for (auto item: substrings){
                if (item.first < minLen) { minLen=item.first; start=item.second; }
            }
            return s.substr(start, minLen);
        } else return "";

    }

    bool t_in_s(vector<int>&t, vector<int>&s){
        for (int i=0; i<52;++i){
            if (s[i]<t[i]){return false;}
        }
        return true;
    }

    int get_index(char ch){
        return ch < 'a'?  (ch- 'A'): ( ch-'a'+26);
    }
};

int main() {
//    string s = "ADOBECODEBANC", t = "ABC";
//    string s = "abc", t = "b";
//    string s = "a", t = "a";
    string s = "cabefgecdaecf" , t = "cae";
    Solution solution;
    auto ans = solution.minWindow(s, t);

//    vector<int> num_s('z'-'A', 0);
//    vector<int> num_t('z'-'A', 0);
//
//    for (auto item : s){
//        ++num_s[item-'A'];
//    }
//    for (auto item : t){
//        ++num_t[item-'A'];
//    }
//    auto tmp = solution.t_in_s(num_t, num_s);
//    cout<<tmp;
//    string ans = string(s.begin(), s.end()-1);

    std::cout <<"ans = "<<ans<<endl;
    return 0;
}


string minWindow(string s, string t)
{
    int hash1[128]={0};
    int kinds=0;
    for(auto ch:t)
    {
        if(hash1[ch]++==0) kinds++;
    }
    int hash2[128]={0};
    int minlen=INT_MAX,begin=-1;

    for(int left=0,right=0,count=0;right<s.size();right++)
    {
        char in=s[right];
        if(++hash2[in]==hash1[in]) count++;//进窗口+维护count
        while(count==kinds)
        {
            if(right-left+1<minlen)
            {
                minlen=right-left+1;
                begin=left;
            }
            char out=s[left++];
            if(hash2[out]--==hash1[out]) count--;
        }
    }
    if (begin==-1) return "";
    else return s.substr(begin,minlen);
}
